package com.shuang.dp13;

import java.util.*;

public class Main {
    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        
        //材料种类
        int n = scanner.nextInt();
        //行李承担总重量 背包容量
        int bagWeight = scanner.nextInt();

        //每种材料的重量和价值
        int[] weight = new int[n];
        int[] value = new int[n];

        for (int i = 0; i < n; i++) {
            weight[i] = scanner.nextInt();
            value[i] = scanner.nextInt();
        }

        //二维dp数组
        int[][] dp = new int[n][bagWeight + 1];

        //递推公式
        //能放下i的情况下:放与不放i取最大值: 放i的情况 因为物品可以无限次放 所以还是从[0,i]物品任选物品放进容量j减去当前物品重量的剩余容量中 
        //dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - weight[i]] + value[i])

        // 初始化
        //第一列容量为0时肯定为0 不用管了
        //第一行 当容量够放物品0时 就要一直放能放多少个放多少个
        for (int j = weight[0]; j <= bagWeight; j++) {
            dp[0][j] = dp[0][j - weight[0]] + value[0];
        }

        // 遍历顺序 
        for (int i = 1; i < n; i++) {
            for (int j = 1; j <= bagWeight; j++) {
                if (j < weight[i]) {
                    //容量不够放物品i 只能
                    dp[i][j] = dp[i - 1][j];
                } else {
                    //够放物品i时 不放与放 取最大
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - weight[i]] + value[i]);
                }
            }
        }

        System.out.println(dp[n - 1][bagWeight]);
        scanner.close();
    }
}